9592. Concatenation of two
palindromes
Find the number
of ways to construct a string of length n
using k Latin letters (the size of
the alphabet is k) as the concatenation
of two nonempty palindromes.
Input. Two positive integers n and k (1 ≤ n ≤ 105, 1 ≤ k ≤ 26).
Output. Print the number of ways to construct the
given string. Print the answer modulo 109 + 7.
Explanation. In the first test case the
string of length 4 using one letter (à for
example) can be constructed in three ways: a + aaa, aa + aa, aaa + a.
|
Sample
input 1 |
Sample
output 1 |
|
4 1 |
3 |
|
|
|
|
Sample
input 2 |
Sample
output 2 |
|
3 2 |
8 |
SOLUTION
exponentiation +
combinatorics
Algorithm analysis
Let’s represent a
string of length n as the
concatenation of two non-empty palindromes of lengths l and n – l. In a palindrome of length l, the first (l + 1) / 2 letters can be chosen arbitrarily (any of the k letters available), and the remaining
letters should be chosen to form a palindrome. This can be done in k(l+1)/2 ways.
Similarly, in a
palindrome of length n – l, the first (n – l + 1) / 2 letters
can be chosen arbitrarily, and the remaining letters should form a palindrome. This can be
done in k(n-l+1)/2 ways.
Constructing the concatenation of two
palindromes with lengths l and n – l can
be done in
k(l+1)/2 * k(n-l+1)/2
ways. Since neither of the palindromes should
be empty, then 1 ≤ l ≤ n – 1. The total number of possible palindromes is
All operations should be carried out modulo
109 + 7.
Algorithm realization
The computations are performed modulo 109 + 7. Let’s
define the modulo MOD.
#define MOD 1000000007
The powmod function computes the value of xn mod m.
long long
powmod(long long x, long long n, long long m)
{
if (n ==
0) return 1;
if (n % 2
== 0) return powmod((x * x) % m, n / 2,
m);
return (x *
powmod(x, n - 1, m)) % m;
}
The main part of the program. Read the input data.
scanf("%d %d",
&n, &k);
Compute the answer res using the
formula.
res = 0;
for (l = 1; l < n; l++)
res = (res +
powmod(k, (l + 1) / 2, MOD) *
powmod(k, (n - l + 1) / 2, MOD)) % MOD;
Print the answer.
printf("%lld\n",
res);
Java realization
import java.util.*;
public class Main
{
public final static long MOD = 1000000007;
static long PowMod(long x, long n, long m)
{
if (n == 0) return 1;
if (n % 2 == 0) return PowMod((x * x) % m, n / 2, m);
return (x * PowMod(x, n - 1, m)) % m;
}
public static void main(String[] args)
{
Scanner con = new Scanner(System.in);
long n = con.nextLong();
long k = con.nextLong();
long res = 0;
for (long l = 1; l < n; l++)
res = (res + PowMod(k, (l + 1) / 2, MOD) *
PowMod(k, (n - l + 1) / 2, MOD)) % MOD;
System.out.println(res);
con.close();
}
}
Python realization
The computations are performed modulo 109 + 7. Let’s
define the modulo mod.
mod = 10 ** 9 + 7
Read the input data.
n, k = map(int, input().split())
Compute the answer res using the formula.
res = 0;
for l in range(1,n):
res = (res + pow(k, (l + 1) // 2, mod)
*
pow(k, (n - l + 1) // 2, mod)) % mod;
Print the answer.
print(res)